package main

import "fmt"

func main() {
	//nums := []int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}
	nums := []int{0, 0, 1}
	moveZeroes(nums)
}

// 283. 移动零
// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//
// 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
// 示例 1:
//
// 输入: nums = [0,1,0,3,12]
// 输出: [1,3,12,0,0]
// 示例 2:
//
// 输入: nums = [0]
// 输出: [0]
func moveZeroes1(nums []int) {
	index := len(nums) - 1 //
	//fmt.Println(index, "<<<index")
	replaceIndex := index
	for idx, num := range nums {
		// 判断最后一个是否为0, 如果为0则往前找
		for i := replaceIndex; i > idx; i-- {
			if nums[i] != 0 {
				replaceIndex = i
				break
			}
		}
		//
		if idx >= replaceIndex {
			break
		}
		if num == 0 {
			tmp := nums[replaceIndex]
			//fmt.Println(replaceIndex, nums[replaceIndex], num, "<<<<<<")
			nums[replaceIndex] = num
			nums[idx] = tmp
		}
	}
}

func moveZeroes2(nums []int) {
	count := len(nums) - 1
	for i := 0; i < count; i++ {
		// 如果为0则移动到队尾
		if nums[i] == 0 { // 当前 i 为需要移动的位置
			// 后面元素往前移动
			tmp := nums[i]
			//
			for j := i; j < count; j++ {
				nums[j] = nums[j+1]
			}
			nums[count] = tmp
			//// 移动完成后往前移动一位
			count--
			// 因往前一位后,后一位不知道是否为0 所以下次还需要从i开始
			i--
			//fmt.Println(nums, "-----")
		}
	}

	fmt.Println(nums)
}

func moveZeroes(nums []int) {
	var j = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[i], nums[j] = nums[j], nums[i]
			j++
		}
	}
	fmt.Println(nums)
}
